package com.sun.javaalgorithm.day03;

/**
 * @version 1.0
 * @Package: com.sun.javaalgorithm.day03
 * @ClassName: Leetcode001
 * @Author: sgq
 * @Date: 2024/4/17 14:16
 * @Description: 反转单链表
 */
public class Leetcode001 {

    /**
     * 一、创建新链表，从旧链表遍历，头结点插入新链表
     *
     * @param head
     * @return
     */
    private static ListNode reverse1(ListNode head) {
        // 1、创建新的空链表
        ListNode newHead = null;
        // 2、原链表没有节点或者只有一个节点直接返回
        if (head == null || head.next == null) {
            return head;
        }
        // 3、循环遍历原链表
        while (head != null) {
            // 4、创建一个新节点，进行头插入
            newHead = new ListNode(head.val, newHead);
            head = head.next;
        }
        return newHead;
    }

    /**
     * 二、旧链表移除头结点，新链表头插入旧链表移除的头结点
     *
     * @param head
     * @return
     */
    private static ListNode reverse2(ListNode head) {
        List listOld = new List(head);
        List listNew = new List(null);
        while (true) {
            ListNode listNode = listOld.removeFirst();
            if (listNode == null) {
                break;
            }
            System.out.println("旧链表移除头结点:" + listNode.val);
            listNew.addFirst(listNode);
        }
        return listNew.head;
    }

    static class List {

        public ListNode head = null;

        public List(ListNode node) {
            head = node;
        }

        /**
         * 头插入节点
         *
         * @param node
         */
        public void addFirst(ListNode node) {
            node.next = head;
            head = node;
        }

        /**
         * 移除头结点
         *
         * @return
         */
        public ListNode removeFirst() {
            ListNode first = null;
            if (head != null) {
                first = head;
                head = head.next;
            }
            return first;
        }

    }

    /**
     * 三、递归反转单链表
     *
     * @param node
     * @return
     */
    private static ListNode reverse3(ListNode node) {
        // 递归结束条件，返回最后一个节点
        if (node.next == null) {
            return node;
        }
        // 递归操作
        ListNode listNode = reverse3(node.next);
        // 递归【归】的过程从后向前将链表指向反转：原来【4->5->null】 改为 【5->4->null】，依次如此，最后整个链表完成反转。
        node.next.next = node;
        node.next = null;
        // 返回链表最后一个节点
        return listNode;
    }

    /**
     * 四、单链表头插入
     * h
     * 1  2  3  4  5
     * o1
     * n1
     * h
     * 2  1  3  4  5
     * o1
     * n1
     *
     * @param head
     * @return
     */
    private static ListNode reverse41(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode n1 = head;
        ListNode o1 = head;
        while (o1.next != null) {
            head = o1.next;
            o1.next = o1.next.next;
            head.next = n1;
            n1 = head;
        }
        return n1;
    }

    /**
     * 四、单链表头插入
     * o2
     * 1  2  3  4  5
     * o1
     * n1
     * o2
     * 2  1  3  4  5
     * o1
     * n1
     *
     * @param o1
     * @return
     */
    private static ListNode reverse42(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode n1 = o1;
        ListNode o2 = o1.next;
        while (o2 != null) {
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        return n1;
    }


    /**
     * 五、二方式的面向过程代码形式 【移旧头结点，头插入到新链表】
     * <p>
     * o1  o2
     * 1   2   3   4   5
     * <p>
     * n1
     * 1  null
     *
     * @param o1
     * @return
     */
    private static ListNode reverse5(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode n1 = null;
//        ListNode o2 = o1.next;
        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
//            o2=o2.next;
        }
        return n1;
    }


    public static void main(String[] args) {
        ListNode listNode05 = new ListNode(5, null);
        ListNode listNode04 = new ListNode(4, listNode05);
        ListNode listNode03 = new ListNode(3, listNode04);
        ListNode listNode02 = new ListNode(2, listNode03);
        ListNode listNode01 = new ListNode(1, listNode02);
        System.out.println(listNode01);
//        ListNode listNode = reverse1(listNode01);
//        ListNode listNode = reverse2(listNode01);
//        ListNode listNode = reverse3(listNode01);
//        ListNode listNode = reverse41(listNode01);
//        ListNode listNode = reverse42(listNode01);
        ListNode listNode = reverse5(listNode01);
        System.out.println(listNode);
    }

}
